package linkedList;

/**
 * 25. K 个一组翻转链表
 * 给你一个链表，每k个节点一组进行翻转，请你返回翻转后的链表。
 * k是一个正整数，它的值小于或等于链表的长度。
 * 如果节点总数不是k的整数倍，那么请将最后剩余的节点保持原有顺序。
 * <p>
 * 进阶：
 * 你可以设计一个只使用常数额外空间的算法来解决此问题吗？
 * 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
 * <p>
 * 限制
 * 列表中节点的数量在范围 sz 内
 * 1 <= sz <= 5000
 * 0 <= Node.val <= 1000
 * 1 <= k <= sz
 */
public class ReverseNodeInKGroup_25 {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        ListNode pre = dummy;
        ListNode end = dummy;
        while (end.next != null) {
            // 经过k次遍历后，end指向第k个节点
            for (int i = 0; i < k && end != null; i++) {
                end = end.next;
            }
            if (end == null) {
                break;
            }

            // 保存end的下一个节点
            ListNode next = end.next;
            // 断开end节点
            end.next = null;
            // 记录要反转的部分链表的头结点
            ListNode start = pre.next;
            // 链表整体的头结点的下一个节点为部分节点反转后的头节点
            pre.next = reverse(start);

        }

        return null;
    }

    // 完全反转链表head，返回反转后的起始节点
    public ListNode reverse(ListNode head) {
        ListNode pre = new ListNode(0);
        pre.next = head;

        ListNode cur = null;
        while (head != null) {
            cur = head;
            head = head.next;
            cur.next = pre;
            pre = cur;
        }
        return pre;
    }
}
